class Solution {
    public int numDecodings(String s) {
        if(s.charAt(0) == '0') return 0;
        int n = s.length();
        // 状态表示
        int[] dp = new int[n + 1];//dp[i] 表示以i位置为结尾的解码方法的总数
        // 初始化
        dp[0] = 1;// 增加一个虚拟节点
        dp[1] = 1;
        // 状态转移方程 - 填表
        for(int i = 1; i < n; i++){
            char ch = s.charAt(i);
            // 单独解码
            if(ch >= '1' && ch <= '9') dp[i + 1] += dp[i];
            // 结合前一个字符解码
            char prev = s.charAt(i - 1);
            int num = (prev - '0') * 10 + (ch - '0');
            if(num >= 10 && num <= 26){
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[n];
    }
}